PC Plus SuperCD (UK) 1994 June/PC Plus Super CD coverdisc Issue 93 June 1994.iso/suprdisk/wilfpw/wordfind.bas

BASIC Source File | 1994-05-31 | 5.2 KB | 192 lines

DEFINT A-Z
DECLARE SUB QuickSort (Low%, High%)
DECLARE SUB GetWordList (FileSpec$)
DECLARE FUNCTION RandInt% (Lower%, Upper%)
DECLARE FUNCTION BinChop (Lower%, Upper%)
DIM SHARED WordList(500) AS STRING
DIM SHARED NumWords%
DIM SHARED Key$

CLS
PRINT "Wait..."
NumWords% = 0
GetWordList ("WORDS.DAT")
QuickSort 0, NumWords% - 1

' Get the key phrase and display closest match

Key$ = ""
DO UNTIL False
    Chop% = BinChop(0, NumWords% - 1)
    IF Chop% <> -1 THEN
        LOCATE 23, 1
        PRINT SPACE$(40)
        LOCATE 23, 1
        PRINT WordList(Chop%)
    END IF

    LOCATE 2, 1
    PRINT "Enter a word to match: "; Key$; " ";
    LOCATE CSRLIN, POS(1) - 1, 1

    ' Read next character

    DO
        X$ = UCASE$(INKEY$)
    LOOP WHILE X$ = ""

    IF (X$ = CHR$(27)) OR (X$ = CHR$(13)) THEN
        EXIT DO
    ELSEIF (X$ = CHR$(8)) OR (X$ = CHR$(0) + CHR$(75)) THEN  'Backspace
        IF LEN(Key$) > 0 THEN
            Key$ = MID$(Key$, 1, LEN(Key$) - 1)
        ELSE
            ' Empty string - can't backup any more
            PRINT CHR$(7)
        END IF
    ELSE
        Key$ = Key$ + X$
    END IF
LOOP
END

' ============================== BinChop ===================================
'   Perform a binary chop on the word list looking for the closest match.
'   The word we're searching for is assumed to be in the Key$ variable.
'   BinChop returns the array index of the found word.
' ============================================================================
'
FUNCTION BinChop (Lower%, Upper%)
    DIM MidPoint AS INTEGER

    ' Firstly, make sure we're in the same ballpark
    IF (Key$ < WordList(Lower%)) OR (Key$ > WordList(Upper%)) THEN
        BinChop = -1
        EXIT FUNCTION
    END IF

    ' Now see if we've converged down to 2/3 elements
    IF Upper% - Lower% <= 1 THEN
        IF Key$ > WordList(Lower%) THEN
            BinChop = Upper%
        ELSE
            BinChop = Lower%
        END IF
        EXIT FUNCTION
    END IF

    ' Haven't converged yet - do the chop
    MidPoint = Lower + ((Upper% - Lower%) / 2)
    IF Key$ = WordList(MidPoint) THEN
        ' What, me - Optimistic ?
        BinChop = MidPoint
    ELSEIF Key$ > WordList(MidPoint) THEN
        BinChop = BinChop(MidPoint, Upper)
    ELSE
        BinChop = BinChop(Lower, MidPoint)
    END IF
END FUNCTION

' ============================== GetWordList =================================
'   This routine opens a file and reads up to 500 words from it into an array.
'   No attempt is made to perform de-duplication of the input.
' ============================================================================
'
SUB GetWordList (FileSpec$)
    DIM I AS INTEGER
    OPEN FileSpec$ FOR INPUT AS #1
    DO
        LINE INPUT #1, Line$
        Line$ = UCASE$(LTRIM$(RTRIM$(Line$)))

        ' Split the line into individual words '

        DO WHILE LEN(Line$) > 0
            I = INSTR(Line$, " ")
            IF I > 0 THEN
                WordList(NumWords%) = LEFT$(Line$, I - 1)
                Line$ = RIGHT$(Line$, LEN(Line$) - I)
            ELSE
                WordList(NumWords%) = Line$
                Line$ = ""
            END IF

            NumWords% = NumWords% + 1
            IF NumWords% = 500 THEN
                CLOSE #1
                EXIT SUB
            END IF
        LOOP
    LOOP UNTIL EOF(1)
    CLOSE #1
END SUB

' ============================== QuickSort ===================================
'   QuickSort works by picking a random "pivot" element in then moving every
'   element that is bigger to one side of the pivot, and every element that
'   is smaller to the other side.  QuickSort is then called recursively with
'   the two subdivisions created by the pivot.  Once the number of elements
'   in a subdivision reaches two, the recursive calls end and the array is sorted.
' ============================================================================
'
SUB QuickSort (Low, High)
    IF Low < High THEN

        ' Only two elements in this subdivision; swap them if they are out of
        ' order, then end recursive calls:

        IF High - Low = 1 THEN
            IF WordList(Low) > WordList(High) THEN
                SWAP WordList(Low), WordList(High)
            END IF
        ELSE

            ' Pick a pivot element at random, then move it to the end:

            RandIndex = RandInt%(Low, High)
            SWAP WordList(High), WordList(RandIndex)
            Partition$ = WordList(High)
            DO
            ' Move in from both sides towards the pivot element:
            I = Low: J = High
            DO WHILE (I < J) AND (WordList(I) <= Partition$)
                I = I + 1
            LOOP
            DO WHILE (J > I) AND (WordList(J) >= Partition$)
                J = J - 1
            LOOP

            ' If we haven't reached the pivot element, it means that two
            ' elements on either side are out of order, so swap them:
            IF I < J THEN
                SWAP WordList(I), WordList(J)
            END IF
        LOOP WHILE I < J

            ' Move the pivot element back to its proper place in the array:

            SWAP WordList(I), WordList(High)

            ' Recursively call the QuickSort procedure (pass the smaller
            ' subdivision first to use less stack space):
            IF (I - Low) < (High - I) THEN
                QuickSort Low, I - 1
                QuickSort I + 1, High
            ELSE
                QuickSort I + 1, High
                QuickSort Low, I - 1
            END IF
        END IF
   END IF
END SUB

' =============================== RandInt% ===================================
'   Returns a random integer greater than or equal to the Lower parameter
'   and less than or equal to the Upper parameter.
' ============================================================================
'
FUNCTION RandInt% (Lower, Upper)
   RandInt% = INT(RND * (Upper - Lower + 1)) + Lower
END FUNCTION